차근차근정확하게

경주로건설

Properties1
tags학습, 코딩테스트, bfsdfs, 프로그래머스, 알고리즘, bfs, 다익스트라

5 min read

경주로건설

NOTE

프로그래머스 Lv3 · BFS(방향 가중치 + 3차원 방문 배열) 단순 최단 거리가 아니라 진입 방향(코너)에 따라 비용이 달라지는 가중치 탐색. 2차원 방문 배열로는 코너 역전 현상을 놓치므로 [행][열][방향] 3차원 방문 배열이 필요하다.

📝 문제

  • 격자에서 출발점(0,0) → 도착점까지 경주로를 건설한다.
  • 직선 도로 1칸 = 100원, 코너(방향 전환) = 500원. 최소 건설 비용을 구한다.

💡 접근

  • 가중치가 방향에 따라 달라지므로 BFS(또는 우선순위 큐 다익스트라)가 DFS보다 압도적으로 유리하다.
  • 상태에 ‘바라보는 방향’을 포함해야 한다: Data(int row, int col, int direction, int cost).
  • 방문 기록을 **3차원 int[row][col][4]**로 두고 모두 Integer.MAX_VALUE로 초기화 → 같은 칸이라도 도착 방향별로 최소 비용을 따로 관리.
  • 비용 갱신 조건: 새 비용이 기존 기록보다 **작거나 같을 때(<=)**만 큐에 넣고 갱신. ‘같을 때’를 허용해야 다음 턴의 코너 역전을 노릴 수 있다.

📎 코너 비용이 600원인 이유 (500 + 100)

한 칸 이동한다는 것은 “다음 칸에 직선 도로(100원)를 새로 깐다”는 뜻이다.

  1. 직진(이전 방향과 같음): 직선 도로를 이어 붙이므로 +100원.
  2. 방향 전환(이전 방향과 다름): 직전 칸에 코너 블록(500원)을 설치하고, 꺾인 방향으로 한 칸 나아가려면 새 직선 도로(100원)도 깔아야 한다 → 500 + 100 = 600원이 한 번에 청구.

한 줄 요약: 자동차는 무조건 한 칸을 움직이므로 기본 이동 비용 100원은 깔고 가고, 핸들을 꺾었다면 코너 설치비 500원이 추가로 붙어 600원이 된다.

📎 오답 노트 (내가 놓쳤던 부분)

  • DFS 백트래킹 상태 오염: count = dfs(...)처럼 재귀 결과를 변수에 덮어써, 막힌 길에서 누적된 비용이 다른 길 탐색에 묻어가는 오류가 났다. (가중치 다른 최단거리 문제는 BFS가 유리.)
  • 비용 계산 오해: 방향이 꺾일 때 코너 비용(500)만 더했다. 실제로는 직진(100) + 코너(500) = 600을 더해야 한다.
  • 코너 역전 현상(2차원 배열의 한계): visited[][](2차원)로 비용을 기록하면, 600원(오른쪽 방향)으로 도착한 차가 500원(아래쪽 방향)짜리 때문에 탐색 종료당한다. 하지만 다음 목표가 ‘오른쪽’이면 600원 차는 직진(100)만, 500원 차는 코너(600)를 돌아야 해 최종적으로 600원 차가 더 싼 경우를 놓친다.

💡 복습 체크리스트 (다시 풀 때 설계)

  1. 3차원 배열 선언: int[행][열][4] visited를 만들고 모두 Integer.MAX_VALUE로 초기화. (마지막 차원 = 도착 시 바라보는 방향 0~3)
  2. 상태 클래스: 큐에 넣을 Data(row, col, direction, cost). (첫 출발 예외: 초기 방향을 특수값으로 두어 첫 칸은 100원만 들도록)
  3. 갱신 조건: 새 비용이 기존 기록보다 작거나 같을 때(<=)만 큐에 넣고 갱신.

⏱️ 복잡도

  • 시간: O(N × N × 4) — 각 칸을 방향별(4)로 최대 한 번씩 처리.
  • 공간: O(N × N × 4) — 3차원 방문 배열.

🔗 관련

그래프 뷰

백링크